package leetcode.editor.cn;

import utils.PrintUtil;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

//[51]N 皇后
public class NQueens51 {
    public static void main(String[] args) {
        Solution solution = new NQueens51().new Solution();

        List<List<String>> lists = solution.solveNQueens(4);
        PrintUtil.print(lists);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<List<String>> res = new ArrayList<>();


        public List<List<String>> solveNQueens(int n) {
//            Set<Integer> colSet = new HashSet<>();
//            Set<Integer> pieSet = new HashSet<>();
//            Set<Integer> naSet = new HashSet<>();
//            int [][] map = new int[n][n];
//            recur(map, n, 0, colSet, pieSet, naSet);


            int[][] qMap = new int[n][n];//0 null, 1 Q
            dfsBit(n, 0, 0, 0, 0, qMap);

            return res;
        }

        //mehod1 	执行耗时:6 ms,击败了24.40% 的Java用户 //	内存消耗:44 MB,击败了25.82% 的Java用户
        private void recur(int[][] map, int n, int row, Set<Integer> colSet, Set<Integer> pie, Set<Integer> na) {
            //stop
            if (row == n) {//current level is 4,up level is 3 ,is checked over.  0,3.valid
                res.add(converToList(map));
                return;
            }

            for (int i = 0; i < n; i++) {
                //current level
                //current row valid
                boolean isValid = checkValid(row, i, colSet, pie, na);
                if (isValid) {
                    map[row][i] = 1;
                    colSet.add(i);
                    int tempNa = row + i;
                    na.add(tempNa);
                    int tempPie = row - i;
                    pie.add(tempPie);

                    //drill down
                    recur(map, n, row + 1, colSet, pie, na);

                    //reverse 清扫状态
                    map[row][i] = 0;
                    colSet.remove(i);
                    na.remove(tempNa);
                    pie.remove(tempPie);
                }
            }
        }
        private boolean checkValid(int row, int col, Set<Integer> colSet, Set<Integer> pie, Set<Integer> na) {
            if (colSet.contains(col)) return false;

            int tempNa = row + col;
            if (na.contains(tempNa)) return false;

            int tempPie = row - col;
            return !pie.contains(tempPie);
        }
        private List<String> converToList(int[][] map) {
            ArrayList<String> strList = new ArrayList<>(map.length);
            for (int i = 0; i < map.length; i++) {//row
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < map[i].length; j++) {
                    if (map[i][j] == 0) {
                        sb.append(".");
                    } else {
                        sb.append("Q");
                    }
                }
                strList.add(sb.toString());
            }
            map = null;
            return strList;
        }


        //bit  执行耗时:1 ms,击败了99.80% 的Java用户  内存消耗:43.9 MB,击败了40.23% 的Java用户
        private void dfsBit(int n, int row, int col, int pie, int na, int[][] qmap) {
            if (row >= n) {
                res.add(converToList(qmap));
                return;
            }

            //can able q
            int bit = (~(col | pie | na) & ((1 << n) - 1));
            while (bit > 0) {
                int tail = bit & (-bit);

                int tailIndex = 0, temp = 1;
                while (tail > temp) {
                    temp = temp << 1;
                    tailIndex++;
                }
                int colIndex = n - 1 - tailIndex;
                qmap[row][colIndex] = 1;
                //重点。。。pie +tail ,na + tail 而不是
                dfsBit(n, row + 1, col | tail, (pie | tail) << 1, (na | tail) >> 1, qmap);
                //clean
                qmap[row][colIndex] = 0;

                bit = bit & (bit - 1);
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}